\section{Conclusion}
We have analyzed two natural gossip-based discovery processes in
networks and showed almost-tight bounds on their convergence in
arbitrary networks.  Our processes are motivated by the resource
discovery problem in distributed networks as well as by the evolution
of social networks.  We would like to study variants of the processes
that take into account failures associated with forming connections,
the joining and leaving of nodes, or having only a subset of
nodes to participate in forming connections.  We believe our
techniques can be extended to analyze such situations as well.  From a
technical standpoint, the main problem left open by our work is to
resolve the logarithmic factor gap between the upper and lower bounds.
It is not hard to show that from the perspective of increasing the
minimum degree by a constant factor, our analysis is tight up to
constant factors.  It is conceivable, however, that a sharper upper
bound can be obtained by an alternative analysis that uses a
``smoother'' measure of progress.
